1. Field of Invention
The present invention generally relates to an interleaving apparatus and method thereof, and more particularly to a grouping bits interleaving apparatus and method thereof.
2. Description of Prior Art
In digital communication systems, information to be transmitted is represented in bits. A bit is a binary digit that can take on two kinds of values namely “0” or “1”. When one bit transmitted by the transmitter with a value is received but decoded as a different value in the receiver, a bit-error has occurred. This kind of error is caused by channel impairments like noise, interference, fading or any combination of them.
In most cases, noise, interference and fading impairments occur in bursts and can lead to more than one bit being in error consecutively. When bit-errors occur in consecutive received bits at the receiver end, a burst-error occurs. In most communication systems, forward error correction (FEC, hereafter) is a method that is used to detect and correct bit-errors, and thus the performances of communication systems will be improved.
However, the ability of FEC for correcting bit-errors is best when the bit-errors are not consecutive. In other words, isolated bit-errors can be more easily detected and corrected by the modem FEC algorithm, device or apparatus, while the consecutive bit-errors are not easily detected and corrected by the modem FEC algorithm, device or apparatus. Interleaving is a common algorithm in the digital communication system, which is used to spread the burst-error to multiple isolated bit errors. Using an appropriated FEC mechanism and an interleaving algorithm, these isolated errors can be corrected and the entire transmit message will be received correctly. At the transmitter end, the mechanism to do the interleaving algorithm is called interleaver; while in receiver end, the mechanism to do the de-interleaving algorithm is called de-interleaver.
Interleaving the transmitted bits and de-interleaving the received bits can spread a long burst-error into several single bit-errors or multiple shorter burst-errors. Then the following FEC algorithm will be more capable to correct these single bit-errors or shorter burst-errors than the longer burst-error.
Please see FIGS. 1A, 1B, 1C and 1D. FIG. 1A is a scheme diagram showing the procedure of writing data into the conventional interleaver 10. FIG. 1B is a scheme diagram showing the procedure of reading data from the conventional interleaver 10. FIG. 1C is a scheme diagram showing the procedure of writing data into the conventional de-interleaver 11. FIG. 1D is a scheme diagram showing the procedure of reading data from the conventional de-interleaver 11. The conventional interleaver 10 and de-interleaver 11 adapt the block-interleaving and block-de-interleaving algorithm.
As shown in FIGS. 1A and 1B, the interleaver 10 at the transmitter end interleaves a plurality of bits of the input data (input of the interleaver 10). The received bits to be interleaved will be written into a storage array (usually a memory) in sequence of rows, and be read from the storage array in sequence of columns.
In FIG. 1A, the input data (input of the interleaver 10) will be written to fill up one row in a fixed direction (see the arrows of FIG. 1A, like from left to right) before being written to the next row. After writing all the bits of the input data, column permutation may be done to sort of scattering the bits, and thus in the transmission the burst-error will be spread into multiple single bit errors or shorter burst-errors dispersedly. In FIG. 1B, the column permuted stored bits can be read out in sequence of columns. In other words, the data stored and permutated in the interleaver 10 will be read out in another fixed direction (see the arrows of FIG. 1B, like from top to bottom) for each column one by one. Thus the function of interleaving at the transmitter end is achieved.
As shown in FIGS. 1C and 1D, the de-interleaver 11 at the receiver end is directly opposite to that of the interleaver 10 at the transmitter end. Received data (symbols) of the de-interleaver 11 to be de-interleaved will be written into another storage array (i.e. the dimension of this storage array is same as that used at the transmitter end) in sequence of columns, and be read out from the storage array in sequence of rows.
In FIG. 1C, the de-interleaver 11 receives the data transmitted from the transmitter end, and the data will be written into the storage array in sequence of columns. Then the de-interleaver 11 de-permutes columns, wherein the de-permutation is opposite to the permutation of the interleaver 10. In FIG. 1D, the stored de-permuted data is read out in sequence of rows as de-interleaved output data from the de-interleaver 11. Thus the function of de-interleaving at the receiver end is achieved.
As stated above, data to be interleaved at the transmitter end are in unit of bits. At the transmitter end, one bit represents one datum. While at the receiver end, the data to be de-interleaved is mostly in the unit of symbols, and one symbol consists of several bits whereby the soft or multi-level values are used by the FEC decoder for better decoding. In some cases where the FEC decoder operates at the binary level, data to be de-interleaved can be in the units of bits. Thus at the receiver end, one bit or several bits represent one datum.
Generally speaking, the storage array (such as memory) is most efficiently composed of words (ex: 16 bits per word in WCDMA systems), where one word may consist of several bits such as 16, 32, or 64 bits. Therefore when designing a de-interleaver for a receiver using soft symbol FEC decoding, it is straightforward to use one word to store one symbol datum.
However, when designing an interleaver for a transmitter or a receiver using a binary FEC decoder, an inefficient usage of memory will occur if one word is still used to store only one bit datum. Besides, memory access time will be too much in such an implementation. With one word only containing one bit datum, the memory access times (i.e. consider writing access only) will be as many as the number of data bits. Additionally, a larger address space is needed.
In essence, the conventional block interleaving implementation using word-based memory suffers from poor memory usage, longer processing time, and larger address space. In order to improve the efficiency of the memory usage as well as access time, the embodiment of the invention provides an interleaving mechanism and a de-interleaving mechanism with the receiver using a binary FEC decoder to possess benefits in digital communication systems.